package com.hjj.dataStructures.linkedList;

/**
 * @author hjj
 * @create 2019-11-17 21:30
 */
public class Josephu {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.add(5);
        circleSingleLinkedList.showChildren();
        // 5 1 2    2->4->1->5->3
        circleSingleLinkedList.countChildren(1,2,5);
    }
}

/**
 * 创建一个环形的单向链表
 * 根据用户的输入，生成一个小孩出圈的顺序
 */
class CircleSingleLinkedList {
    // 创建一个first节点
    private Children first = new Children(-1);

    // 添加小孩节点，构建一个环形的链表
    public void add(int num) {
        if (num < 1) {
            System.out.println("num：" + num + " 值不正确");
            return;
        }
        // 辅助指针，帮助构建环形链表
        Children curentChildren = null;
        // 使用for循环
        for (int i = 1; i <= num; i++) {
            // 根据编号创建第一个小孩
            Children children = new Children(i);
            if (i == 1) {
                first = children;
                first.setNext(first);
                curentChildren = first; // 让currentChildren指向第一个小孩
            } else {
                curentChildren.setNext(children);
                children.setNext(first);
                curentChildren = children;
            }
        }
    }

    // 遍历当前的环形链表
    public void showChildren() {
        if (isEmpty()) return;
        // 因为first不能动，因此仍然使用一个辅助指针完成遍历
        Children currentChildren = first;
        while (true) {
            System.out.println("小孩的编号：" + currentChildren.getNo());
            if (currentChildren.getNext() == first) {
                break;
            }
            // 让currentChildren后移
            currentChildren = currentChildren.getNext();
        }
    }

    /**
     * 根据用户的输入，计算出小孩出圈的顺序
     *
     * @param startNo  表示从第几个小孩开始
     * @param countNum 表示数几下
     * @param nums     表示最初有多少个小孩
     */
    public void countChildren(int startNo, int countNum, int nums) {
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("参数输入有误，请重新输入");
            return;
        }
        // 创建辅助指针，帮助完成小孩出圈
        Children helper = first;
        // 让helper指向最后环形中的最后一个节点
        while (helper.getNext() != first) {
            helper = helper.getNext();
        }
        System.out.println("helper: " + helper);
        // 报数前，让first和helper移动k-1次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        System.out.println("报数前，让first和helper移动：" + (startNo -1));
        // 当报数时，让first和helper指针同时的移动m-1次，然后出圈
        while (true) {
            // 说明圈中只有一个小孩
            if (helper == first) break;
            // 让first和helper指针同时的移动countNum-1
            for (int i = 0; i < countNum - 1; i++) {
                helper = helper.getNext();
                first = first.getNext();
            }
            // 这时first指向的节点，就是要出圈的小孩节点
            System.out.println("小孩 " + first.getNo() + " 出圈");
            // 将first指向的小孩节点出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后留在圈中的小孩节点：" + first.getNo());
    }

    public boolean isEmpty() {
        if (first == null) {
            System.out.println("链表为空");
            return true;
        } else {
            return false;
        }
    }


}

/**
 * 创建Children，表示一个节点
 */
class Children {
    private int no;
    private Children next;

    public Children(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Children getNext() {
        return next;
    }

    public void setNext(Children next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Children{" +
                "no=" + no +
//                ", next=" + next +
                '}';
    }
}
